package main

import "sort"

type Price struct {
	timestamp int
	price     int
}

type StockPrice struct {
	timestampMap map[int]*Price // point to same structure in priceOrder
	priceOrder   []*Price
	current      *Price
}

func Constructor() StockPrice {
	return StockPrice{
		timestampMap: map[int]*Price{},
	}
}

func (this *StockPrice) Update(timestamp int, price int) {
	p := &Price{
		timestamp: timestamp,
		price:     price,
	}
	// update current
	if this.current == nil || this.current.timestamp <= timestamp {
		this.current = p
	}
	exist := this.timestampMap[timestamp]
	this.timestampMap[timestamp] = p
	if exist != nil {
		// remove old from price order
		for i, x := range this.priceOrder {
			if x == exist {
				copy(this.priceOrder[i:], this.priceOrder[i+1:])
				this.priceOrder = this.priceOrder[:len(this.priceOrder)-1]
				break
			}
		}
	}

	// insert into price order
	pivot := sort.Search(len(this.priceOrder), func(i int) bool {
		return this.priceOrder[i].price >= price
	})
	this.priceOrder = append(this.priceOrder, nil)
	copy(this.priceOrder[pivot+1:], this.priceOrder[pivot:])
	this.priceOrder[pivot] = p
}

func (this *StockPrice) Current() int {
	return this.current.price
}

func (this *StockPrice) Maximum() int {
	return this.priceOrder[len(this.priceOrder)-1].price
}

func (this *StockPrice) Minimum() int {
	return this.priceOrder[0].price
}


func main() {
	stock := Constructor()
	stock.Update(1, 10)
	stock.Update(2, 5)
	println(stock.Current())
	println(stock.Maximum())
	stock.Update(1, 3)
	stock.Update(4, 2)

}